package com.cat.graphTheory;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/word-search/
 * @create 2025/9/22 17:47
 * @since JDK17
 */

public class Solution19 {
    boolean[][] vis;
    int n, m, len;
    boolean ans;
    String word;
    char[][] board;
    int[][] d = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    void dfs(int x, int y, int cur) {
        if (cur + 1 == word.length()) {
            ans = true;
            return;
        }
        vis[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + d[i][0], ny = y + d[i][1];
            if (nx == -1 || nx >= n || ny == -1 || ny == m || vis[nx][ny] || board[nx][ny] != word.charAt(cur + 1)) {
                continue;
            }
            dfs(nx, ny, cur + 1);
        }
        vis[x][y] = false;
    }
    public boolean exist(char[][] board, String word) {
        n = board.length;
        m = board[0].length;
        len = word.length();
        this.board = board;
        this.word = word;
        vis = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == word.charAt(0)) {
//                    for (int k = 0; k < n; k++) {
//                        Arrays.fill(vis[k], false);
//                    }
                    dfs(i, j, 0);
                    if (ans) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
}
